package OfferLanQiaoBei.a_12届蓝桥真题;
/*
给定一个括号序列，要求尽可能少地添加若干括号使得括号序列变得合法，当添加完成后，会产生不同的添加结果，请问有多少种本质不同的添加结果。
两个结果是本质不同的是指存在某个位置一个结果是左括号，而另一个是右括号。
例如，对于括号序列 ((()，只需要添加两个括号就能让其合法，有以下几种不同的添加结果：()()()、()(())、(())()、(()()) 和 ((()))。

输入格式
输入一行包含一个字符串 s，表示给定的括号序列，序列中只有左括号和右括号。

输出格式
输出一个整数表示答案，答案可能很大，请输出答案除以 1000000007(即 10e+7) 的余数。

数据范围
对于 40%的评测用例，|s|≤200。
对于所有评测用例，1≤|s|≤5000。

输入样例：
((()

输出样例：
5
 */
import java.util.*;
import java.io.*;
/*
我只看懂了80%
临考前2天我只看懂了80%
 */
public class j括号序列 {
	public static void main(String[] args) {
		j括号序列 test = new j括号序列();
		test.useDeal();
	}
	
	public void useDeal() {
		Scanner scanner = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
		String string = scanner.next();
		final int MOD = (int) 1e9 + 7;
		int length = string.length();
		char[] arr = new char[length + 1];
		long[][] dp = new long[5010][5010];//dp矩阵足够大
		deal(dp, arr, length, MOD, string);
	}
	
	public void deal(long[][] dp, char[] arr, int length, int MOD, String string) {
		for (int i = 1; i <= length; i++) {//从下标为1开始
			arr[i] = string.charAt(i - 1);
		}
		long left = cacl(dp, arr, length, MOD, string);
		//--------从这里
		for (int i = 1; i <= length; i++) {
			if (string.charAt(length - i) == '(') {
				arr[i] = ')';
			} else {
				arr[i] = '(';
			}
		}
		//--------到这里，是反转字符串
		long right = cacl(dp, arr, length, MOD, string);
		System.out.println(left * right % MOD);//最后的结果是两种添加的数量，相乘
	}
	
	public long cacl(long[][] dp, char[] arr, int length, int MOD, String string) {
		for (int i = 0; i <= length; i++) {//初始化dp
			Arrays.fill(dp[i], 0);
		}
		dp[0][0] = 1;//默认值：什么括号都没有情况下，‘(’比‘)’多0个；合法
		for (int i = 1; i <= length; i++) {//一个括号一个括号的判断
			if (arr[i] == '(') {					//左括号情况
				for (int j = 1; j <= length; j++) {//不用考虑dp[i][0] 因为dp[i-1][-1]是不合法的情况 不存在 为0
					dp[i][j] = dp[i - 1][j - 1];//递推公式；就这里是最难想到的；死记硬背
				}
			} else {								//右括号情况
				//右括号情况的dp[i][0]需要特殊设置；根据递推公式，当j=0，那么dp[i][0] = dp[i-1][0] + dp[i-1][1]
				dp[i][0] = (dp[i - 1][0] + dp[i - 1][1]) % MOD;//特判防止越界 这里数据短，用的是优化前的推断
				for (int j = 1; j <= length; j++) {
					dp[i][j] = (dp[i - 1][j + 1] + dp[i][j - 1]) % MOD;//递推公式；就这里是最难想到的；死记硬背
				}
			}
		}
		for (int i = 0; i <= length; i++) {//我们需要的就是长度为len添加括号的合法情况，
			if (dp[length][i] > 0) {//而从前往后遍历出现的第一个有可能的情况就是需要括号数最少的情况，
				return dp[length][i];//因为左括号可以加很多个，我们仅需添加最少的情况
			}
		}
		return -1;//肯定能找到最小的合法种类；这个-1是永远不会给出的
	}
}
